1. Field of the Invention
The present invention relates to a communication network such as an ad hoc network comprising a plurality of communication terminals, to the terminals in the network, and in particular to the routing method employed in the network.
2. Description of the Related Art
Communication in an ad hoc network takes place by the routing of packets from a source terminal to a destination terminal on a path that may lead through one or more intermediate or relay terminals. All of the terminals in the network are capable of operating as routers, that is, of designating the paths or routes that packets will follow. The routing methods employed in an ad hoc network include both single-path and multipath schemes.
Conventional single-path routing decreases the amount of usage of network resources by selecting a single path between the source terminal and the destination terminal and switching data on that path as described in, for example, Japanese Unexamined Patent Application Publication No. H8-37535. The problem with single-path routing is that if a terminal on the single designated path drops out because, for example, its battery runs down, or because the terminal moves to another location, the path is broken and communication ceases. Another path must then be set up to continue the communication. The single-path communication process therefore tends to be unstable with frequent interruptions.
In conventional multipath routing, a complex process is carried out in advance to select a plurality of paths between the source terminal and the destination terminal, and data switching is carried out on those paths, as described in, for example, Japanese Unexamined Patent Application Publication No. 2001-237875. The plurality of communication paths reduces the likelihood of communication interruptions, because a failure on one path can generally be dealt with by immediately switching to another path, but the complex processing required to define the paths and make them available imposes a burden on the computational resources of the terminals. An additional problem is that the multiple paths tend to converge near the source and destination terminals, reducing path redundancy in these areas and making radio interference a problem. A further problem is that when communication is stable, multipath routing wastes network resources. This further problem could be overcome by switching between single-path routing and multipath routing, but that would only increase the complexity of the routing control process.
Further information can be found in U.S. Pat. No. 6,028,857 and in an article by Marina et al. entitled ‘On-demand Multipath Distance Vector Routing in Ad Hoc Networks’ published by the University of Cincinnati in 2001.
The problems of the conventional single-path and multipath routing schemes can be summarized as follows. Since single-path routing uses a single path, if a terminal on the path becomes unavailable because it has moved to another location or exhausted its battery charge, the path is broken, communication is cut off, and a new path must be set up before communication can resume. Communication therefore tends to be unstable. Although conventional multipath routing schemes can deal with such path breakdowns because they provide a plurality of communication paths, they also involve much control overhead: paths are selected through a complex computational process, and the paths have to be set up by an elaborate control process. Conventional multipath routing therefore tends to squander network resources. It would be desirable to have a multipath routing scheme that is more easily controlled and does not make such heavy use of network resources.